package jtg.generator.path;

import soot.Unit;
import soot.toolkits.graph.UnitGraph;

import java.util.*;

public class PrimePathCoverage {
    private UnitGraph unitGraph;
    private Set<List<Unit>> primePaths;

    public Set<List<Unit>> getPrimePaths() {
        return primePaths;
    }

    public PrimePathCoverage(UnitGraph unitGraph){
        this.unitGraph=unitGraph;
        this.primePaths=calPrimePathComplete(this.unitGraph);
    }
    //采用深度优先算法
    private static void dfs(UnitGraph ug, Unit current, List<Unit> currentPath, Set<List<Unit>> allPaths, Set<Unit> visited) {
        // 将当前节点添加到路径
        currentPath.add(current);

        // 如果当前节点是尾节点，则将路径添加到结果列表或者首尾相同
        if (ug.getTails().contains(current)||(currentPath.size()>1&&currentPath.get(0)==current)) {

            allPaths.add(new ArrayList<>(currentPath));
        } else {
            // 获取当前节点的后继节点
            List<Unit> successors = ug.getSuccsOf(current);

            // 递归遍历后继节点
            for (Unit successor : successors) {
                if (!visited.contains(successor)) {
                    visited.add(successor);
                    dfs(ug, successor, currentPath, allPaths, visited);
                    visited.remove(successor); // 在回溯时移除已访问标记
                }
                else{
                    allPaths.add(new ArrayList<>(currentPath));
                }
            }
        }

        // 在回溯之前，将当前节点从路径中移除
        currentPath.remove(currentPath.size() - 1);
    }

    /**
     * 返回基路径的List<Unit>
     * 完整的
     */
    public static Set<List<Unit>> calPrimePathComplete(UnitGraph ug){
        Map<String,Integer > map=new HashMap<String, Integer>();
        //构造一个map存放节点和基本快的对应关系
        int index=0;
        for(Unit unit:ug){
            String uid=getID(unit);
            index+=1;
            map.put(uid,index);
        }
        System.out.println(map);//检查一下
        // 用于存储所有基路径的列表
        Set<List<Unit>> allPaths = new HashSet<>();
        // 用于跟踪已访问的节点
        Set<Unit> visited = new HashSet<>();
        // 获取控制流图的入口节点
        List<Unit> heads = ug.getHeads();
        // 对每个节点进行深度优先搜索
        for (Unit head : ug) {
            dfs(ug, head, new ArrayList<>(), allPaths, visited);
        }

        Set<List<Unit>> pathsToRemove=new HashSet<>();
        //remove subpaths
        for(List<Unit> sub1:allPaths){
            for(List<Unit> sub2:allPaths){
                if(sub1!=sub2&&isSubpath(sub1,sub2)){
                    //如果sub1是sub2的子路径
                    pathsToRemove.add(sub1);
                }
            }
        }
        allPaths.removeAll(pathsToRemove);


        int pathNum=0;
        // 打印所有基路径,这是我们学过的基路径,包括循环
        // 但是循环的路径不是完整的，无法直接求解
        System.out.println("这是课上学过的基路径计算：");
        for (List<Unit> path : allPaths) {
            pathNum+=1;
            List<Integer> pathWithIndex=new ArrayList<Integer>();
            for(Unit unit:path){
                String uid=getID(unit);
                int idx=map.get(uid);
                pathWithIndex.add(idx);
            }
            System.out.println("Prime Path: " + path);
            System.out.println("Prime Path "+pathNum+" in Index: "+pathWithIndex);
        }

        // 对于循环路径要扩展成完整的
        Set<List<Unit>> allCompletePaths=new HashSet<>();
        System.out.println("将基路径扩展成完整路径过程：");
        pathNum=0;
        List<Unit> preceeds=new ArrayList<>();
        List<Unit> succeeds=new ArrayList<>();
        for(List<Unit> path:allPaths){
            pathNum+=1;
            //找到并添加前继
            if(!ug.getHeads().contains(path.get(0))){
                preceeds=extendPreds(ug,path);
                List<Integer> preceedsWithIndex=new ArrayList<Integer>();
                //对应到数字节点
                assert preceeds != null;
                for(Unit unit:preceeds){
                    String uid=getID(unit);
                    int idx=map.get(uid);
                    preceedsWithIndex.add(idx);
                }
                System.out.println("这是路径"+pathNum+"的前继："+preceedsWithIndex);
                //拼接所有前继
                preceeds.remove(0);//去掉第一个节点因为本来的path里面就有
                Collections.reverse(preceeds);//逆序
                path.addAll(0,preceeds);//加到最前面

            }
            //找到并添加后继
            if(!ug.getTails().contains(path.get(path.size()-1))){//判断最后一个是不是尾节点
                succeeds=extendSuccs(ug,path);
                List<Integer> succeedsWithIndex=new ArrayList<Integer>();
                //对应到数字节点
                assert succeeds != null;
                for(Unit unit:succeeds){
                    String uid=getID(unit);
                    int idx=map.get(uid);
                    succeedsWithIndex.add(idx);
                }
                System.out.println("这是路径"+pathNum+"的后继："+succeedsWithIndex);
                //拼接后继
                succeeds.remove(0);
                path.addAll(succeeds);
            }
            allCompletePaths.add(path);//处理完的完整路径加到allCompletePaths中
        }

        //打印完整路径
        System.out.println("这是由上面的基路径扩展成的完整路径：");
        pathNum=0;
        for (List<Unit> path : allCompletePaths) {
            pathNum+=1;
            List<Integer> pathWithIndex=new ArrayList<Integer>();
            for(Unit unit:path){
                String uid=getID(unit);
                int idx=map.get(uid);
                pathWithIndex.add(idx);
            }
            System.out.println("Prime Path: " + path);
            System.out.println("Prime Path "+pathNum+" in Index: "+pathWithIndex);
        }
        return allCompletePaths;
    }

    /**
     * 拓展后继节点到tails出口
     * @param ug
     * @param path
     * @return
     */
    private static List<Unit> extendSuccs(UnitGraph ug, List<Unit> path) {
        Unit last=path.get(path.size()-1);//获得要扩展的path的最后一个节点，就是扩展开始点
        List<Unit> succs=ug.getSuccsOf(last);
        if(succs==null || succs.isEmpty()){
            return null;
        }
        boolean isFound=false;
        List<List<Unit>> allSuccsPath=new ArrayList<>();//存放所有的后继路径
        List<Unit> oneSuccsPath=new ArrayList<>();//某一条后继路径
        oneSuccsPath.add(last);
        allSuccsPath.add(oneSuccsPath);//先把第一个节点加上
        List<Unit> succsReturn=new ArrayList<>();//返回值
        while(!isFound){
            allSuccsPath.remove(oneSuccsPath);//拿出第一条路径
            List<Unit> temp=new ArrayList<>(oneSuccsPath);
            Unit current=oneSuccsPath.get(oneSuccsPath.size()-1);//当前路径的最后一个节点
            succs=ug.getSuccsOf(current);//该节点的所有后继
            //遍历每一个后继加到这条路径上，然后将这个路径add到所有后继路径中
            for(Unit succ:succs){
                List<Unit> temp2=new ArrayList<>(temp);
                temp2.add(succ);
                if(ug.getTails().contains(succ)){//如果发现遍历到尾节点就停止
                    isFound=true;
                    succsReturn=temp2;
                }
                else{//否则将该路径加到所有后继路径中
                    allSuccsPath.add(temp2);
                }
            }
            oneSuccsPath=allSuccsPath.get(0);//每次要处理的路径从第一个取，在最开始把第一个路径remove掉，加的时候都加在最后，保证每个路径都有机会被遍历。
        }
        return succsReturn;
    }

    /**
     * 拓展前继节点到heads入口
     * @param ug
     * @param path
     */
    private static List<Unit> extendPreds(UnitGraph ug, List<Unit> path) {
        Unit start=path.get(0);
        List<Unit> preds=ug.getPredsOf(start);
        if(preds==null|| preds.isEmpty()){
            return null;
        }
        boolean isFound=false;
        List<List<Unit>> allPredsPath=new ArrayList<>();
        List<Unit> onePredsPath=new ArrayList<>();
        onePredsPath.add(start);
        allPredsPath.add(onePredsPath);
        List<Unit> predsReturn=new ArrayList<>();
        while(!isFound){
            allPredsPath.remove(onePredsPath);
            List<Unit> temp=new ArrayList<>(onePredsPath);//?
            Unit current=onePredsPath.get(onePredsPath.size()-1);//因为add是加在后面所以是反过来的
            preds=ug.getPredsOf(current);
            for(Unit pred:preds){
                List<Unit> temp2=new ArrayList<>(temp);
                temp2.add(pred);

                if(ug.getHeads().contains(pred)){
                    isFound=true;
                    predsReturn=temp2;

                }
                else {
                    allPredsPath.add(temp2);
                }
            }
            onePredsPath=allPredsPath.get(0);
        }
        return predsReturn;
    }



    private static boolean isSubpath(List<Unit> pi, List<Unit> pj) {
        if (pi == null || pj == null) {
            return false;
        }

        int subIndex = 0;
        int seqIndex = 0;

        while (subIndex < pi.size() && seqIndex < pj.size()) {
            if (pi.get(subIndex).equals(pj.get(seqIndex))) {
                subIndex++;
            }
            seqIndex++;
        }

        // If subIndex is equal to the length of subsequence,
        // then all elements of subsequence are found in sequence in order.
        return subIndex == pi.size();
    }

    /**
     * 获得每个块的id
     * 它将哈希码中的每个数字字符映射为一个小写字母，生成一个新的字符串。
     * @param a
     * @return
     */
    private static String getID(Object a) {
//      String id = Integer.toString(System.identityHashCode(a));
        String id = Integer.toString(a.hashCode());
        StringBuilder newId = new StringBuilder();
        for (int i = 0; i < id.length(); i++) {
            newId.append((char) (97 + id.codePointAt(i) - "0".codePointAt(0)));//计算将数字字符映射为小写字母的偏移量，97 对应 'a' 的 Unicode 编码。
        }
        return newId.toString();
    }
}
